#define ElemType int

#include "common.h"

typedef struct TrieNode {
	unsigned pass;
	unsigned end;
	struct TrieNode** next;
} trie_node;

trie_node* init_node()
{
	trie_node* node = calloc(1, sizeof(trie_node));
	node->next = calloc(26, sizeof(trie_node*));
	node->pass = 0;
	node->end = 0;
	return node;
}

void free_node(trie_node* node)
{
	for (int i = 0; i < 26; i++)
		if (node->next[i])
			free_node(node->next[i]);
	free(node);
}

typedef struct {
	trie_node* root;
} WordDictionary;

WordDictionary* wordDictionaryCreate()
{
	WordDictionary* wd = calloc(1, sizeof(WordDictionary));
	wd->root = init_node();
	return wd;
}

void wordDictionaryAddWord(WordDictionary* obj, char* word)
{
	if (word[0] == '\0')
		return;

	trie_node* node = obj->root;
	node->pass++;
	for (int i = 0, path = 0; word[i] != '\0'; i++) {
		path = word[i] - 'a';
		if (node->next[path] == NULL)
			node->next[path] = init_node();
		node = node->next[path];
		node->pass++;
	}
	node->end++;
}

bool search(trie_node* node, char* word)
{
	for (int i = 0, path = 0; word[i] != '\0'; i++) {
		if (word[i] == '.') {
			for (int j = 0; j < 26; j++) {
				if (node->next[j])
					if (search(node->next[j], word + i + 1))
						return true;
			}
			return false;
		} else {
			path = word[i] - 'a';
			if (!node->next[path])
				return false;
			node = node->next[path];
		}
	}
	return node->end;
}

bool wordDictionarySearch(WordDictionary* obj, char* word)
{
	//if (word[0] == '\0')
	//	return false;

	return search(obj->root, word);
}

void wordDictionaryFree(WordDictionary* obj)
{
	free(obj->root);
	free(obj);
}

int main()
{
	return 0;
}
